package algorithm.templates;

import java.util.*;

public class FruitBasketTemplate {
    public static int minFruitCost(int n, int m, int s, int[] fruits) {
        // dp[i]表示前i个水果的最小成本
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;  // 空集成本为0

        // 单调队列
        Deque<Integer> maxQueue = new LinkedList<>();
        Deque<Integer> minQueue = new LinkedList<>();

        for (int i = 1; i <= n; i++) {
            maxQueue.clear();
            minQueue.clear();

            // 从i逆推j，寻找最优分割点
            for (int j = i; j >= Math.max(1, i - m + 1); j--) {
                // 维护最大值队列（单调递减）
                while (!maxQueue.isEmpty() && fruits[maxQueue.peekLast() - 1] <= fruits[j - 1]) {
                    maxQueue.pollLast();
                }
                maxQueue.offerLast(j);

                // 维护最小值队列（单调递增）
                while (!minQueue.isEmpty() && fruits[minQueue.peekLast() - 1] >= fruits[j - 1]) {
                    minQueue.pollLast();
                }
                minQueue.offerLast(j);

                // 获取最大值u和最小值v
                int u = fruits[maxQueue.peekFirst() - 1];
                int v = fruits[minQueue.peekFirst() - 1];

                // 计算当前区间的成本
                int basketCost = (i - j + 1) * ((u + v) / 2) + s;

                // 更新dp[i]，取最小值
                dp[i] = Math.min(dp[i], dp[j - 1] + basketCost);
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取输入
        int n = sc.nextInt();
        int m = sc.nextInt();
        int s = sc.nextInt();
        int[] fruits = new int[n];
        for (int i = 0; i < n; i++) {
            fruits[i] = sc.nextInt();
        }

        // 计算最小成本并输出
        System.out.println(minFruitCost(n, m, s, fruits));
    }
}
